<html><!-- Created using the cpp_pretty_printer from the dlib C++ library.  See http://dlib.net for updates. --><head><title>dlib C++ Library - graph_utils_abstract.h</title></head><body bgcolor='white'><pre>
<font color='#009900'>// Copyright (C) 2007  Davis E. King (davis@dlib.net)
</font><font color='#009900'>// License: Boost Software License   See LICENSE.txt for the full license.
</font><font color='#0000FF'>#undef</font> DLIB_GRAPH_UTILs_ABSTRACT_
<font color='#0000FF'>#ifdef</font> DLIB_GRAPH_UTILs_ABSTRACT_

<font color='#0000FF'>#include</font> "<a style='text-decoration:none' href='../directed_graph.h.html'>../directed_graph.h</a>"
<font color='#0000FF'>#include</font> "<a style='text-decoration:none' href='../algs.h.html'>../algs.h</a>"

<font color='#0000FF'>namespace</font> dlib
<b>{</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> T
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'>typename</font> T::edge_type<font color='#5555FF'>&amp;</font> <b><a name='edge'></a>edge</b><font face='Lucida Console'>(</font>
        T<font color='#5555FF'>&amp;</font> g,  
        <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> i, 
        <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> j
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - T is an implementation of graph/graph_kernel_abstract.h 
            - g.has_edge(i,j)
        ensures
            - returns a reference to the edge data for the edge connecting nodes i and j
              (i.e. returns g.node(i).edge(x) such that g.node(i).neighbor(x).index() == j)
    !*/</font>

    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> T
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'>typename</font> <font color='#0000FF'>const</font> T::edge_type<font color='#5555FF'>&amp;</font> <b><a name='edge'></a>edge</b><font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> T<font color='#5555FF'>&amp;</font> g,  
        <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> i, 
        <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> j
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - T is an implementation of graph/graph_kernel_abstract.h 
            - g.has_edge(i,j)
        ensures
            - returns a const reference to the edge data for the edge connecting nodes i and j
              (i.e. returns g.node(i).edge(x) such that g.node(i).neighbor(x).index() == j)
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> T
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'>typename</font> T::edge_type<font color='#5555FF'>&amp;</font> <b><a name='edge'></a>edge</b><font face='Lucida Console'>(</font>
        T<font color='#5555FF'>&amp;</font> g,  
        <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> parent_idx, 
        <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> child_idx 
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - T is an implementation of directed_graph/directed_graph_kernel_abstract.h 
            - g.has_edge(parent_idx,child_idx)
        ensures
            - returns a reference to the edge data for the directed edge connecting parent
              node g.node(parent_idx) to child node g.node(child_idx).
    !*/</font>

    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> T
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'>typename</font> <font color='#0000FF'>const</font> T::edge_type<font color='#5555FF'>&amp;</font> <b><a name='edge'></a>edge</b><font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> T<font color='#5555FF'>&amp;</font> g,  
        <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> parent_idx, 
        <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> child_idx 
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - T is an implementation of directed_graph/directed_graph_kernel_abstract.h 
            - g.has_edge(parent_idx,child_idx)
        ensures
            - returns a const reference to the edge data for the directed edge connecting 
              parent node g.node(parent_idx) to child node g.node(child_idx).
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> T
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>bool</u></font> <b><a name='graph_has_symmetric_edges'></a>graph_has_symmetric_edges</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> T<font color='#5555FF'>&amp;</font> graph
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - T is an implementation of directed_graph/directed_graph_kernel_abstract.h 
        ensures
            - if (All nodes have either 0 edges between them or 2 edges between them.  
              That is, if there is an edge pointing from node A to node B then there is
              also an edge from B to A) then
                - returns true
            - else
                - returns false
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> T
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>bool</u></font> <b><a name='graph_contains_directed_cycle'></a>graph_contains_directed_cycle</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> T<font color='#5555FF'>&amp;</font> graph
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - T is an implementation of directed_graph/directed_graph_kernel_abstract.h 
        ensures
            - if (there is a directed cycle in the given graph) then
                - returns true
            - else
                - returns false
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> T
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>bool</u></font> <b><a name='graph_contains_undirected_cycle'></a>graph_contains_undirected_cycle</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> T<font color='#5555FF'>&amp;</font> graph
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - T is an implementation of directed_graph/directed_graph_kernel_abstract.h or
              T is an implementation of graph/graph_kernel_abstract.h
        ensures
            - if (there is an undirected cycle in the given graph) then
                - returns true
            - else
                - returns false
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> T
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>bool</u></font> <b><a name='graph_contains_length_one_cycle'></a>graph_contains_length_one_cycle</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> T<font color='#5555FF'>&amp;</font> graph
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - T is an implementation of directed_graph/directed_graph_kernel_abstract.h or
              T is an implementation of graph/graph_kernel_abstract.h
        ensures
            - if (it is the case that graph.has_edge(i,i) == true for some i) then
                - returns true
            - else
                - returns false
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> src_type,
        <font color='#0000FF'>typename</font> dest_type 
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> <b><a name='copy_graph_structure'></a>copy_graph_structure</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> src_type<font color='#5555FF'>&amp;</font> src,
        dest_type<font color='#5555FF'>&amp;</font> dest
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - src_type is an implementation of directed_graph/directed_graph_kernel_abstract.h or
              src_type is an implementation of graph/graph_kernel_abstract.h
            - dest_type is an implementation of directed_graph/directed_graph_kernel_abstract.h or
              dest_type is an implementation of graph/graph_kernel_abstract.h
            - dest_type is not a directed_graph when src_type is a graph
        ensures
            - this function copies the graph structure from src into dest
            - #dest.number_of_nodes() == src.number_of_nodes()
            - for all valid i: #dest.node(i).item has an initial value for its type
            - for all valid i and j:
                - if (src.has_edge(i,j) == true) then
                    - #dest.has_edge(i,j) == true
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> src_type,
        <font color='#0000FF'>typename</font> dest_type 
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> <b><a name='copy_graph'></a>copy_graph</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> src_type<font color='#5555FF'>&amp;</font> src,
        dest_type<font color='#5555FF'>&amp;</font> dest
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - src_type is an implementation of directed_graph/directed_graph_kernel_abstract.h or
              src_type is an implementation of graph/graph_kernel_abstract.h
            - dest_type is an implementation of directed_graph/directed_graph_kernel_abstract.h or
              dest_type is an implementation of graph/graph_kernel_abstract.h
            - src_type and dest_type are both the same kind of graph.  That is, they
              are either both directed or both undirected.
            - the node and edge data in the graphs are copyable via operator=().
        ensures
            - #dest is a complete duplicate of src.
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> directed_graph_type,
        <font color='#0000FF'>typename</font> graph_type
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> <b><a name='create_moral_graph'></a>create_moral_graph</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> directed_graph_type<font color='#5555FF'>&amp;</font> g,
        graph_type<font color='#5555FF'>&amp;</font> moral_graph
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - directed_graph_type is an implementation of directed_graph/directed_graph_kernel_abstract.h
            - graph_type is an implementation of graph/graph_kernel_abstract.h
            - graph_contains_directed_cycle(g) == false
        ensures
            - #moral_graph == the moralized version of the directed graph g
            - #moral_graph.number_of_nodes() == g.number_of_nodes()
            - for all valid i and j:
                - if (g.has_edge(i,j) == true) then
                    - #moral_graph.has_edge(i,j) == true
                      (i.e. all the edges that are in g are also in moral_graph)
            - for all valid i:
                - for all pairs p1 and p2 such that p1 != p2 and g.node(p1) and g.node(p2) are both
                  parents of node g.node(i):
                    - #moral_graph.has_edge(p1,p2) == true
                      (i.e. all the parents of a node are connected in the moral graph)
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> T,
        <font color='#0000FF'>typename</font> S
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> <b><a name='find_connected_nodes'></a>find_connected_nodes</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> T<font color='#5555FF'>&amp;</font> n,
        S<font color='#5555FF'>&amp;</font> visited
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - T is a node_type from an implementation of directed_graph/directed_graph_kernel_abstract.h or
              T is a node_type from an implementation of graph/graph_kernel_abstract.h
            - S is an implementation of set/set_kernel_abstract.h
        ensures
            - let G be the graph that contains node n
            - #visited.is_member(n.index()) == true
            - for all i such that there is an undirected path from n to G.node(i):
                - #visited.is_member(i) == true
            - for all i such that visited.is_member(i):
                - #visited.is_member(i) == true
                  (i.e. this function doesn't remove anything from visited.  So if
                  it contains stuff when you call this function then it will still
                  contain those things once the function ends)
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> T 
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>bool</u></font> <b><a name='graph_is_connected'></a>graph_is_connected</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> T<font color='#5555FF'>&amp;</font> g
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - T is an implementation of directed_graph/directed_graph_kernel_abstract.h or
              T is an implementation of graph/graph_kernel_abstract.h
        ensures
            - every node in g has an undirected path to every other node in g.  
              I.e. g is a connected graph
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> graph_type,
        <font color='#0000FF'>typename</font> sets_of_int
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>bool</u></font> <b><a name='is_clique'></a>is_clique</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> graph_type<font color='#5555FF'>&amp;</font> g,
        <font color='#0000FF'>const</font> sets_of_int<font color='#5555FF'>&amp;</font> clique
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - graph_type is an implementation of graph/graph_kernel_abstract.h
            - sets_of_int is an implementation of set/set_kernel_abstract.h
              and it contains unsigned long objects. 
            - graph_contains_length_one_cycle(g) == false
            - for all x such that clique.is_member(x):
                - x &lt; g.number_of_nodes()
        ensures
            - if (it is true that for all i and j such that clique.is_member(i) and 
              clique.is_member(j) then g.has_edge(i,j) == true) then
                - returns true
            - else
                - returns false
            - if (clique.size() == 0) then
                - returns true
                  (this is just a special case of the above condition)
            - else
                - returns false
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> graph_type,
        <font color='#0000FF'>typename</font> sets_of_int
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>bool</u></font> <b><a name='is_maximal_clique'></a>is_maximal_clique</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> graph_type<font color='#5555FF'>&amp;</font> g,
        <font color='#0000FF'>const</font> sets_of_int<font color='#5555FF'>&amp;</font> clique
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - graph_type is an implementation of graph/graph_kernel_abstract.h
            - sets_of_int is an implementation of set/set_kernel_abstract.h
              and it contains unsigned long objects. 
            - graph_contains_length_one_cycle(g) == false
            - for all x such that clique.is_member(x):
                - x &lt; g.number_of_nodes()
            - is_clique(g,clique) == true
        ensures
            - if (there is no x such that clique.is_member(x) == false 
              and g.has_edge(i,x) for all i such that cliques.is_member(i)) then
                - returns true
            - else
                - returns false
            - if (clique.size() == 0) then
                - returns true
                  (this is just a special case of the above condition)
            - else
                - returns false
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> graph_type,
        <font color='#0000FF'>typename</font> set_of_sets_of_int
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> <b><a name='triangulate_graph_and_find_cliques'></a>triangulate_graph_and_find_cliques</b> <font face='Lucida Console'>(</font>
        graph_type<font color='#5555FF'>&amp;</font> g,
        set_of_sets_of_int<font color='#5555FF'>&amp;</font> cliques
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - graph_type is an implementation of graph/graph_kernel_abstract.h
            - set_of_sets_of_int is an implementation of set/set_kernel_abstract.h
              and it contains another set object which is comparable by operator&lt; and
              itself contains unsigned long objects.  
              (e.g. set&lt;set&lt;unsigned long&gt;::compare_1a&gt;::kernel_1a)
            - graph_contains_length_one_cycle(g) == false
            - graph_is_connected(g) == true
        ensures
            - #g.number_of_nodes() == g.number_of_nodes()
            - all this function does to g is add edges to it until g becomes a 
              chordal graph where a chordal graph is a graph where each cycle
              in the graph of 4 or more nodes has an edge joining two nodes
              that are not adjacent in the cycle. 
            - #cliques.size() == the number of maximal cliques in the graph #g
            - for all valid sets S such that #cliques.is_member(S):
                - for all valid integers i and j such that S.is_member(i) == true
                  and S.is_member(j) == true and i != j:
                    - #g.has_edge(i,j) == true
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> graph_type,
        <font color='#0000FF'>typename</font> join_tree_type
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>bool</u></font> <b><a name='is_join_tree'></a>is_join_tree</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> graph_type<font color='#5555FF'>&amp;</font> g,
        <font color='#0000FF'>const</font> join_tree_type<font color='#5555FF'>&amp;</font> join_tree
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - graph_type is an implementation of directed_graph/directed_graph_kernel_abstract.h or
              graph_type is an implementation of graph/graph_kernel_abstract.h
            - join_tree_type is an implementation of graph/graph_kernel_abstract.h
            - join_tree_type::type is an implementation of set/set_compare_abstract.h and
              this set type contains unsigned long objects. 
            - join_tree_type::edge_type is an implementation of set/set_compare_abstract.h and
              this set type contains unsigned long objects. 
            - graph_contains_length_one_cycle(g) == false
            - graph_is_connected(g) == true
        ensures
            - if (join_tree is a valid join tree of graph g.  That is, join_tree is a 
              tree decomposition of g) then
                - returns true
            - else
                - returns false

            - a join tree of graph g is defined as follows: 
                - graph_contains_undirected_cycle(join_tree) == false
                - graph_is_connected(join_tree) == true
                - for all valid i:
                    - join_tree.node(i).item == a non-empty set containing node indexes 
                      from g.  That is, this set contains all the nodes from g that are
                      in this cluster in the join tree
                - for all valid i and j such that i and j are both &lt; join_tree.number_of_nodes()
                    - let X be the set of numbers that is contained in both join_tree.node(i).item
                      and join_tree.node(j).item
                    - It is the case that all nodes on the unique path between join_tree.node(i)
                      and join_tree.node(j) contain the numbers from X in their sets.
                    - edge(join_tree,i,j) == a set containing the intersection of 
                      join_tree.node(i).item and join_tree.node(j).item
                - the node index for every node in g appears in some node in join_tree at 
                  least once.
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> graph_type,
        <font color='#0000FF'>typename</font> join_tree_type
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> <b><a name='create_join_tree'></a>create_join_tree</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> graph_type<font color='#5555FF'>&amp;</font> g,
        join_tree_type<font color='#5555FF'>&amp;</font> join_tree
    <font face='Lucida Console'>)</font>;
    <font color='#009900'>/*!
        requires
            - graph_type is an implementation of graph/graph_kernel_abstract.h
            - join_tree_type is an implementation of graph/graph_kernel_abstract.h
            - join_tree_type::type is an implementation of set/set_compare_abstract.h and
              this set type contains unsigned long objects. 
            - join_tree_type::edge_type is an implementation of set/set_compare_abstract.h and
              this set type contains unsigned long objects. 
            - graph_contains_length_one_cycle(g) == false
            - graph_is_connected(g) == true
        ensures
            - #is_join_tree(g, join_tree) == true
    !*/</font>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
<b>}</b>

<font color='#0000FF'>#endif</font> <font color='#009900'>// DLIB_GRAPH_UTILs_ABSTRACT_
</font>

</pre></body></html>